// 给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

// 案例 1:

// 输入: 
//     5
//    / \
//   3   6
//  / \   \
// 2   4   7

// Target = 9

// 输出: True
 

// 案例 2:

// 输入: 
//     5
//    / \
//   3   6
//  / \   \
// 2   4   7

// Target = 28

// 输出: False

#include "../stdc++.h"

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// 深度优先搜索（前序遍历） + 哈希表
class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        if (root == nullptr) {
            return false;
        }
        if (hashSet.count(k - root->val) > 0) {
            return true;
        }
        hashSet.insert(root->val);
        return findTarget(root->left, k) || findTarget(root->right, k);
    }
private:
    unordered_set<int> hashSet;
};

// 广度优先搜索（层序遍历）+ 哈希表
class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        if (root == nullptr) {
            return false;
        }
        unordered_set<int> hashSet;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            if (hashSet.count(k - node->val) > 0) {
                return true;
            }
            hashSet.insert(node->val);
            if (node->left != nullptr) {
                q.push(node->left);
            }
            if (node->right != nullptr) {
                q.push(node->right);
            }
        }
        return false;
    }
};

// 深度优先搜索 + 中序遍历 + 双指针
class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        inorderTraversal(root);
        int n = nums.size();
        int left = 0;
        int right = n - 1;
        while (left < right) {
            int sum = nums[left] + nums[right] ;
            if (sum == k) {
                return true;
            } else if (sum < k) {
                ++left;
            } else if (sum > k) {
                --right;
            }
        }
        return false;
    }
private:
    vector<int> nums;
    void inorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        inorderTraversal(root->left);
        nums.push_back(root->val);
        inorderTraversal(root->right);
    }
};

// 迭代 + 中序遍历 + 双指针
class Solution {
public:
    TreeNode *getLeft(stack<TreeNode *> &stk) {
        TreeNode *root = stk.top();
        stk.pop();
        TreeNode *node = root->right;
        while (node != nullptr) {
            stk.push(node);
            node = node->left;
        }
        return root;
    }

    TreeNode *getRight(stack<TreeNode *> &stk) {
        TreeNode *root = stk.top();
        stk.pop();
        TreeNode *node = root->left;
        while (node != nullptr) {
            stk.push(node);
            node = node->right;
        }
        return root;
    }

    bool findTarget(TreeNode *root, int k) {
        TreeNode *left = root, *right = root;
        stack<TreeNode *> leftStack, rightStack;
        leftStack.push(left);
        while (left->left != nullptr) {
            leftStack.push(left->left);
            left = left->left;
        }
        rightStack.push(right);
        while (right->right != nullptr) {
            rightStack.push(right->right);
            right = right->right;
        }
        while (left != right) {
            if (left->val + right->val == k) {
                return true;
            }
            if (left->val + right->val < k) {
                left = getLeft(leftStack);
            } else {
                right = getRight(rightStack);
            }
        }
        return false;
    }
};
